Effective load balancing for processing packets arriving as different flows has been a continuing problem in the field of networking. This load balancing may be necessary on intermediate network elements (e.g., path and link load balancing in routers/switches) or network elements closer to end points (e.g., server load balancing which front end server farms). Of late, the role of flow load balancing has only become more important with the advent of Software Defined Networking (SDN) systems (e.g., OpenFlow), where the processing of a packet is defined per flow.
Traditionally, a load balancer receives arriving packets and dispatches these packets to packet processing servers such that the packet-processing load is balanced across the servers. For example, on a services router (such as a Smart Services Router™ manufactured by Telefonaktiebolaget LM Ericsson of Stockholm, Sweden), a line card acts as the load balancer and the components that process packets on flows (e.g., perform Deep Packet Inspection (DPI)) on services cards act as the servers. In such devices, the line card receives traffic over its traffic ports and must dispatch the traffic across the service cards for further processing, which is dependent on the service type the packet belongs to.
One common algorithm for load balancing is Round Robin Scheduling, which sprays requests (e.g., packets) to different servers according to a defined ordering of the servers. Some round robin algorithms also attempt to take the load on each server into consideration before routing requests to them, so servers experiencing large loads may be skipped. Typically, the decision to route a request to a specific server results in creation of “session” state in the load balancer to ensure that all packets that belong to a particular session/flow get routed to the same server instance.
Per-packet load balancing provides a very granular level of load balancing across the servers. However, per-packet load balancing is not typically used in networking systems as it suffers from significant disadvantages, including a mandatory maintenance of all flow processing states in all servers, packet re-ordering issues, etc.
A commonly used alternative to per-packet load balancing is to employ some kind of hash mechanism using the flow identifier (typically the Internet Protocol version 4 (IPv4) or Transmission Control Protocol/Internet Protocol (TCP/IP) “5-tuple”—source IP address, destination IP address, source port, destination port, protocol) of each packet to distribute packets across the servers. The load balancer applies this hash to header field values of received packets, and packets belonging to the same hash bucket will be sent to the same server. Thus, this process ensures that packets on a given flow are always directed to the same server, as their header field values representing the flow identifier will always result in a same result from the application of the hash function. Although this method does not require any flow state maintenance within the load balancer, it may lead to skewed load distributions because the assignment of flows to servers does not take the existing load on the servers into account. Further, moving flows across servers is generally quite complex, or impossible, as flow assignment is based on a fixed hashing algorithm.
A more flexible per-flow load balancing mechanism would be to enable the load balancer to maintain mappings between flows and the assigned server for each flow (i.e., the server that “owns” the processing of the flow). Using such a mechanism, when a packet arrives on a flow at the load balancer, the mapping can be looked-up to dispatch the packet to the assigned server (assuming that the flow has already been assigned to a server). However, the role of the load balancer in this scenario mandates the maintenance of large mapping tables on the load balancer. To maintain the server assignment for every flow, the load balancer theoretically would need to maintain up to the order of 2^(13*8) entries for traditional IPv4 5-tuple flow identifiers, which is not practical for implementation in most load balancers due to table size scaling issues. For example, hardware commonly used for such purposes may, e.g., support only a 64 Kilobyte (K) table for the maintenance of flow entries, which is far too small for this purpose.
Thus, maintaining mappings for per-flow load balancing introduces one of the biggest limitations in any load balancer in terms of the scale it can support, as the flow table, where the saved session information is stored, is directly in the packet processing fast path and thus the storage space for such mappings is inherently limited. Several techniques have been used to attempt to remedy this storage problem, including maintaining a shadow flow table in DRAM and aging out the flows in the hardware flow table. Another technique includes algorithmically identifying long-lived and high volume flows as “elephant flows” and then instantiating session state only for those flows in the hardware flow table. Other similar approaches also exist that also focus upon solving the same problem of scaling up the load balancer by reducing the amount of session state created in the packet forwarding fast path. While these solutions alleviate the problem, they fall short of solving them completely primarily because they are still aimed at maintaining per-session state and can only achieve scale by reducing the number of sessions for which state needs to be maintained.
Accordingly, new techniques for per-flow load balancing that are both flexible, load-considerate, and state efficient are needed.